package DifficultPractice;

import org.junit.Test;

public class Demo312 {
//	312. 戳气球
//	有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
//
//	现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 
//	这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
//
//	求所能获得硬币的最大数量。
	
	public int maxCoins(int[] nums) {
		int n = nums.length;
		int[] coins = new int[n+2];	//两端填充1  解决边界问题
		int[][] dp = new int[n+2][n+2];
		int m = coins.length;
		//动态规划 ：
		//dp定义：i到j之间（开区间）的最大金币
		//状态：i和j
		//选择：开区间内的这些  那个是最后一个戳
		//转移方程：dp[i][j] = (k)max(dp[i][k] + dp[k][j] + coins[i]*coins[j]*coins[k])
		coins[0] = 1;
		coins[n+1] = 1;
		for(int i=1; i<=n; i++) {
			coins[i] = nums[i-1];
		}
		
		for(int i=m-3; i>=0; i--) {
			for(int j=i+2; j<=m-1; j++) {
				//选择k最后去戳
				for(int k=i+1; k<=j-1; k++) {
					dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + coins[i]*coins[k]*coins[j]);
				}
			}
		}
		
		return dp[0][n+1];
		
    }
	
	@Test
	public void test_312() {
		maxCoins(new int[] {3,1,5,8});
		
		for(int i=1; i<=5000; i++) {
			System.out.print(i+",");
		}
	}

}
